import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 57. 插入区间
 * https://leetcode-cn.com/problems/insert-interval/
 */
public class Solutions_57 {
    public static void main(String[] args) {
//        int[][] intervals = {{1, 3}, {6, 9}};
//        int[] newInterval = {2, 5};  // output: {{1, 5}, {6, 9}}

//        int[][] intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
//        int[] newInterval = {4, 8};  // output: {{1, 2}, {3, 10}, {12, 16}}

//        int[][] intervals = {};
//        int[] newInterval = {5, 7};  // output: {{5, 7}}

//        int[][] intervals = {{1, 5}};
//        int[] newInterval = {6, 8};  // output: {{1, 5}, {6, 8}}

//        int[][] intervals = {{3, 5}, {12, 15}};
//        int[] newInterval = {6, 6};  // output: {{3, 5}, {6, 6}, {12, 15}}

//        int[][] intervals = {{1, 5}};
//        int[] newInterval = {2, 3};  // output: {{1, 5}}

        int[][] intervals = {{2, 5}, {6, 7}, {8, 9}};
        int[] newInterval = {0, 1};  // output: {{0, 1}, {2, 5}, {6, 7}, {8, 9}}

        int[][] result = insert(intervals, newInterval);
        System.out.println(Arrays.deepToString(result));
    }

    public static int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        boolean insert = false;
        int left = newInterval[0], right = newInterval[1];

        for (int[] interval : intervals) {
            if (interval[1] < left) {
                // 在插入区间的左侧
                res.add(interval);
            } else if (interval[0] > right) {
                // 在插入区间的右侧，且未插入过，那么执行插入操作
                if (!insert) {
                    res.add(new int[]{left, right});
                    insert = true;
                }
                res.add(interval);
            } else {
                // 合并区间
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!insert) {
            // intervals 为空，或者 intervals 遍历结束都未执行过插入操作
            // 那么插入到最后
            res.add(new int[]{left, right});
        }
        return res.toArray(new int[res.size()][]);
    }
}
